
// 1. 用递归或非递归的方法建立一棵二叉树。
// 2. 用递归实现二叉树的先序、中序、后序三种遍历。
// 3. 求二叉树的深度、叶子结点的个数。
// 4. 设计一个选择式菜单，以菜单方式实现各种操作。

#include "stdio.h"
#include <stdlib.h>

typedef int ElementType;

// 定义树的存储结构
typedef struct Tree
{
    ElementType data;
    // 左子
    struct TreeNode *left;
    // 右子
    struct TreeNode *right;
} TreeNode;

// 创建一颗树,返回根节点指针
TreeNode *CreatTree(TreeNode **root)
{
    int inputValue;
    scanf("%d", &inputValue);
    if (inputValue == 0)
    {
        // 此时为空节点
        *root = NULL;
    }
    else
    {
        // 此时不为空
        *root = (TreeNode *)malloc(sizeof(TreeNode));
        (*root)->data = inputValue;
        printf("请输入%d结点的左孩子\n", (*root)->data);
        CreatTree(&((*root)->left));
        printf("请输入%d结点的右孩子\n", (*root)->data);
        CreatTree(&((*root)->right));
    }
}

// 先序遍历二叉树
void preOrder(TreeNode *root)
{
    if (root == NULL)
    {
        // 空树直接 return
        return;
    }
    else
    {
        // 操作处理
        printf("%d ", root->data);
        // 处理左孩子
        preOrder(root->left);
        // 处理右孩子
        preOrder(root->right);
    }
}

// 中序遍历
void inOrder(TreeNode *root)
{
    if (root == NULL)
    {
        return;
    }
    else
    {
        // 先处理左边孩子
        inOrder(root->left);
        // 操作处理
        printf("%d ", root->data);
        // 处理右边孩子
        inOrder(root->right);
    }
}

// 后序遍历
void postOrder(TreeNode *root)
{
    if (root == NULL)
    {
        return;
    }
    else
    {
        // 先处理左边孩子
        postOrder(root->left);
        // 然后处理右边孩子
        postOrder(root->right);
        // 操作处理
        printf("%d ", root->data);
    }
}

// 树的高度
int TreeHeigh(TreeNode *root)
{
    int lh, rh;
    if (root == NULL)
    {
        return 0;
    }
    else
    {
        lh = TreeHeigh(root->left);
        rh = TreeHeigh(root->right);
    }
    // 结点高度是高的那一个加上根节点1
    if (lh > rh)
    {
        return lh + 1;
    }
    else
    {
        return rh + 1;
    }
    return 1;
}

// 树的叶子结点个数
int leafNum(TreeNode *root)
{
    int lnum, rnum;
    if (root == NULL)
    {
        return 0;
    }
    else
    {
        // 没有左右孩子的话那就是叶子结点
        if (root->left == NULL && root->right == NULL)
            return 1;
    }
    // 递归获取左子树的叶子结点
    lnum = leafNum(root->left);
    // 递归获取右子树的叶子结点
    rnum = leafNum(root->right);
    return lnum + rnum;
}

int main()
{
    TreeNode *root;
    // CreatTree(&root);
    // preOrder(root);
    // printf("\n");
    // inOrder(root);
    // printf("\n");
    // postOrder(root);
    // printf("\n");
    // printf("树的高度是%d\n", TreeHeigh(root));
    // printf("树的叶子结点的个数是%d\n", leafNum(root));

    int k;
    do
    {
        printf("\n\n\n\n");
        printf("\t\t\t  树 子系统\n");
        printf("\t\t******************************\n");
        printf("\t\t*        1----建二叉树　 　　*\n");
        printf("\t\t*        2----前序遍历 　　　*\n");
        printf("\t\t*        3----中序遍历　 　　*\n");
        printf("\t\t*        4----后序遍历　 　　*\n");
        printf("\t\t*        5----求树高度     　*\n");
        printf("\t\t*        6----叶子个数 　   *\n");
        printf("\t\t*        0----返　　回　 　　*\n");
        printf("\t\t******************************\n");
        printf("\t\t 请选择菜单项(0－5)：");
        scanf("%d", &k);
        getchar();
        if (k == 1)
        {
            printf("\n 请输入此树的根结点:");
            //建立二叉树
            CreatTree(&root);
        }
        else if (k == 2)
        {
            printf("\n   此树前序遍历的顺序:");
            preOrder(root);
        }
        else if (k == 3)
        {
            printf("\n   此树中序遍历的顺序:");
            inOrder(root);
        }
        else if (k == 4)
        {
            printf("\n   此树后序遍历的顺序:");
            postOrder(root);
        }
        else if (k == 5)
        {
            printf("\n此树的高度是：%d", TreeHeigh(root));
        }
        else if (k == 6) //输出链表
        {
            printf("\n此树叶子结点个数是：%d", leafNum(root));
        }
    } while (k != 0);

    return 0;
}